This invention relates to the field of computer systems. More particularly, a system and methods are provided for load balancing computations, or portions of a computation, among processors in a multiprocessor system.
In a multiprocessor computer, or other tightly coupled system comprising multiple processors, each processor has access to memory for storing and working on data. Such memory may be dedicated to a particular processor (e.g., a local cache) or may be shared among a plurality of processors.
When the multiprocessor system is employed to perform a computation, different processors may be used to execute different portions of the computation. For example, one processor may be close to an edge of the system and have the most efficient connection to an external communication link. That processor may therefore be favored to perform processing that requires external communication. Another processor may be faster than other processors, and thus be more efficient at performing difficult calculations that require little or no input/output.
Thus, when determining how to route a computation in a multiprocessor system—i.e., how to divide the portions or steps of the computation among the processors—the strengths of the various processors may be considered. In addition, however, the costs associated with performing computational steps at different processors must also be considered. In particular, the cost of moving data between different areas of memory, so that different processors can use the data, must be considered. Congestion in the system must also be considered, along with how heavily tasked the various processors are, and so on.
Unfortunately, existing methods of determining how to route a computation among multiple processors are limited to computations that are deterministic—computations in which the steps of the computation are aligned serially, with no branching. In particular, if a computation may involve different steps or different sequences of steps during different executions, existing methods cannot provide adequate routing. Meanwhile, the computations that can benefit most from a multiprocessor environment (e.g., modeling, simulation) are least likely to execute in a deterministic fashion.
Thus, there is a need for a system and a method for determining how to route a multi-step computation among processors in a multiprocessor environment, wherein execution of the computation can branch among different paths.